﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution347
{
    public int[] TopKFrequent(int[] nums, int k)
    {

       
        Dictionary<int, int> map = new Dictionary<int, int>();
        IList<int> list = new List<int>();
        for (int i = 0; i < nums.Length; i++)
        {


            if (map.ContainsKey(nums[i]))
            {

                map[nums[i]]++;

            }
            else
            {
                map[nums[i]] = 1;
                list.Add(nums[i]);
            }
        }
        int[] fre = list.ToArray();





        MakeBigHeap(fre, map);


        for(int i = 0; i < fre.Length; i++)
        {
            Console.Write(fre[i]+",");
        }
        Console.WriteLine();
        IList<int> reslist = new List<int>();

        for (int curlen = fre.Length - 1; curlen >= fre.Length - k; curlen--)
        {
            reslist.Add(fre[0]);
           

            MySwap(fre, 0, curlen );
            for (int i = 0; i < fre.Length; i++)
            {
                Console.Write(fre[i] + ",");
            }
            Console.WriteLine();
            AdjustHeap(0, fre, map, curlen);
            for (int i = 0; i < fre.Length; i++)
            {
                Console.Write(fre[i] + ",");
            }
            Console.WriteLine();

        }

        return reslist.ToArray();


    }
    void MakeBigHeap(int[] nums, Dictionary<int, int> map)
    {

        for (int i = nums.Length / 2; i >= 0; i--)
        {


            AdjustHeap(i, nums, map, nums.Length);
        }

    }

    void AdjustHeap(int i, int[] nums, Dictionary<int, int> map, int len)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int bigger = i;
        if (left < len && map[nums[left]] > map[nums[bigger]])
        {

            bigger = left;
        }
        if (right < len && map[nums[right]] > map[nums[bigger]])
        {

            bigger = right;
        }
        
        if (bigger != i)
        {
            MySwap(nums,bigger, i);
            AdjustHeap(bigger, nums, map, len);
        }




    }

    void MySwap(int[] nums, int i, int j)
    {

        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;


    }






}
class Program347
{

    static void Main347(string[] args)
    {

        int[] nums = [ 2, 2, 3,1, 1, 1,];
        int k = 2;
        Solution347 solution = new Solution347();
        solution.TopKFrequent(nums, k);
    }
}